package edu.uci.ics.multicast.overlay;

import java.util.LinkedList;
import java.util.List;

public class KimAlgorithm {

	private Topology topology;
	private int tNeightbor;
	private double tDistance;
	
	/**
	 * @param overlayNode (input overlay)
	 * @param listM_CandidatesOverlayNodes
	 * @param tNeighbor
	 */
	public KimAlgorithm(Topology topology, int tNeighbor, double tDistance) {
		this.topology = topology;
		this.tNeightbor = tNeighbor;
		this.tDistance = tDistance;
	}
	
	public List<OverlayNode> selectNeighbors(OverlayNode overlayNode, List<OverlayNode> listM_CandidatesOverlayNodes) {
		List<OverlayNode> listN_SelectedNeighbors = new LinkedList<OverlayNode>(); // N
		
		double minLatency = Double.MAX_VALUE;
		OverlayNode e = listM_CandidatesOverlayNodes.get(0); // this list is never empty
		for (OverlayNode m : listM_CandidatesOverlayNodes) {
			double latency = topology.getLatency(overlayNode, m);
			if (latency<minLatency) {
				minLatency = latency;
				e = m;
			}
		}
		listN_SelectedNeighbors.add(e);
		listM_CandidatesOverlayNodes.remove(e);
		
		while (listN_SelectedNeighbors.size()<tNeightbor) {
			int minCorrM = Integer.MAX_VALUE;
			e = listM_CandidatesOverlayNodes.get(0);
			for (OverlayNode m : listM_CandidatesOverlayNodes) {
				int corrM = 0;
				for (OverlayNode n : listN_SelectedNeighbors) {
					corrM = corrM + corr(overlayNode, m, n);
					if (corrM<minCorrM) {
						minCorrM = corrM;
						e = m;
					}
				}
			}
			listN_SelectedNeighbors.add(e);
			listM_CandidatesOverlayNodes.remove(e);
		}
		return listN_SelectedNeighbors;
	}

	private int corr(OverlayNode overlayNode, OverlayNode m, OverlayNode n) {
		List<PhysicalNode> listM_PhysicalNode = topology.getListPhysicalNodes(overlayNode,m);
		List<PhysicalNode> listN_PhysicalNode = topology.getListPhysicalNodes(overlayNode,n);
		int proximityFactor = 0;
		for (PhysicalNode Rmi : listM_PhysicalNode) {
			for (PhysicalNode Rnj : listN_PhysicalNode) {
				if (distance(Rmi,Rnj)<tDistance) {
					proximityFactor = proximityFactor + 1;
				}
			}
		}
		return proximityFactor;
	}

	private double distance(PhysicalNode Rmi, PhysicalNode Rmj)
	{
		double dx   = Rmi.getX() - Rmj.getX(); //horizontal difference 
		double dy   = Rmi.getY() - Rmj.getY(); //vertical difference 
		double dist = Math.sqrt( dx*dx + dy*dy ); //distance using Pythagoras theorem
		return dist;
	}
	
}
